package algorithms.question.class05;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串，返回所有子序列列表
 *
 * @author guichang
 * @date 2021/8/2
 */

@SuppressWarnings("all")
public class Code5_字符串的全排列子序列 {

    public static void main(String[] args) {
        String str = "gui";
        MyUtil.print(allSubString(str));
    }

    /**
     * 时间复杂度 O(2^N)
     * 每个位置只有选和不选两种可能
     */
    public static List<String> allSubString(String str) {
        if (str == null) {
            return null;
        }
        List<String> list = new ArrayList<>();
        process(str.toCharArray(), 0, "", list);
        return list;
    }

    /**
     * 递归获取所有子序列
     *
     * @param cs    字符串的char数组
     * @param index 当前来到了index位置
     * @param path  选择的路径
     * @param list  所有子序列列表
     */
    private static void process(char[] cs, int index, String path, List<String> list) {
        // 选择完了
        if (index == cs.length) {
            list.add(path);
            return;
        }
        // 选择index位置的字符
        process(cs, index + 1, path + cs[index], list);
        // 不选择index位置的字符
        process(cs, index + 1, path, list);
    }

}